package com.bo.day20231221;

import java.util.HashMap;

/**
 * 测试链接：https://leetcode.com/problems/copy-list-with-random-pointer/
 * 一种特殊的单链表节点类描述如下
 * class Node {
 * int value;
 * Node next;
 * Node rand;
 * Node(int val) { value = val; }
 * }
 * rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节点，也可能指向null。
 * 给定一个由Node节点类型组成的无环单链表的头节点 head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。
 * 【要求】
 * 时间复杂度O(N)，额外空间复杂度O(1)
 * 实现思路：
 * 比如：
 * 1 -> 2 -> 3
 * 1.rand = 3;
 * 2.rand = 1;
 * 3.rand = 3;
 * 1. 生成克隆节点,每个节点的next指针都指向他的克隆节点,克隆节点指向源节点的下个节点
 * 就是这个样子： 1 -> 1` -> 2 -> 2` -> 3 -> 3`
 * 2. 调整克隆节点的rand指针
 * 就是这个样子：1`.rand = 1.rand.next;
 * 3.节点分离出来
 * 1->2->3
 * 1`->2`->3`
 *
 * @Author: gpb
 * @Date: 2023/12/22 14:29
 * @Description:
 */
public class CopyListWithRandom {

    public static void main (String[] args) {
        Node node = new Node(1);
        node.next = new Node(2);
        node.next.next = new Node(3);
        Node head = node;
        while (head != null) {
            Node copy = new Node(head.val);
            Node next = head.next;
            head.next = copy;
            copy.next = next;
            head = next;
        }
        Node h = node;
        while (h != null) {
            System.out.println(h.val);
            h = h.next;
        }
        System.out.println();
        Node cur = node;
        // 克隆出来节点
        Node res = node.next;
        while (cur != null) {
            // 原理的下一个节点
            Node next = cur.next.next;
            // 克隆节点
            Node copy = cur.next;
            // 链接克隆节点
            copy.next = next != null ? next.next : null;
            // 复原原理节点
            cur.next = next;
            // 往下移动
            cur = next;
        }
        System.out.println();
    }

    /**
     * 克隆链表
     *
     * @param head
     * @return
     */
    public static Node copyRandomList (Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        // 1. 生成克隆节点,每个节点的next指针都指向他的克隆节点,克隆节点指向源节点的下个节点
        while (cur != null) {
            // 克隆节点
            Node copy = new Node(cur.val);
            // 记录下一个节点
            Node next = cur.next;
            // 当前节点下个指针指向克隆节点
            cur.next = copy;
            // 克隆节点的下个节点指向源节点的下个节点
            copy.next = next;
            // 记录下个解析
            cur = next;
        }
        //  2. 调整克隆节点的rand指针
        //  就是这个样子：1`.rand = 1.rand.next;
        cur = head;
        while (cur != null) {
            Node copy = cur.next;
            copy.random = cur.random != null ? cur.random.next : null;
            cur = cur.next.next;
        }
        // 3.节点分离出来
        cur = head;
        // 克隆出来节点
        Node res = head.next;
        while (cur != null) {
            // 原理的下一个节点
            Node next = cur.next.next;
            // 克隆节点
            Node copy = cur.next;
            // 链接克隆的节点;
            copy.next = next != null ? next.next : null;
            // 复原原理链表
            cur.next = next;
            cur = next;
        }
        return res;
    }

    /**
     * 克隆链表
     *
     * @param head
     * @return
     */
    public static Node copyRandomListMap (Node head) {
        if (head == null) {
            return null;
        }
        // key 存储链表数据
        // value 存储克隆出来的数据
        HashMap<Node, Node> map = new HashMap<>();
        // 创建克隆对象
        Node cur = head;
        while (cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        // 维护链表
        cur = head;
        while (cur != null) {
            Node copy = map.get(cur);
            // 设置克隆的下个链表位置
            copy.next = map.get(copy.next);
            // 设置克隆的random指针
            copy.random = map.get(copy.random);
            cur = cur.next;
        }
        return map.get(head);
    }

    public static class Node {
        int val;
        Node next;
        Node random;

        Node (int val) {
            this.val = val;
        }
    }

}
